package LintCode;

/**
 * @Classname NumberOfSubstringsWithAllZeroes
 * @Description TODO
 * @Date 2021/3/3 15:00
 * @Created by ASUS
 */
public class NumberOfSubstringsWithAllZeroes {
    /*
        给出一个只包含0或1的字符串str,请返回这个字符串中全为0的子字符串的个数
        例1:

        输入:"00010011"
        输出:9
        解释:
        "0"子字符串有5个,
        "00"子字符串有3个,
        "000"子字符串有1个。
        所以返回9

        例2:

        输入:"010010"
        输出:5
     */

    /**
     * @param str: the string
     * @return: the number of substrings
     */
    public int stringCount(String str) {
        // Write your code here.
        if (str == null || str.length() == 0) return 0;
        if (!str.contains("0")) return 0;
        int res = 0;
        for (int i = 0, j = 0; j < str.length(); ) {
            if (str.charAt(i) == '0') {
                while (j < str.length() && str.charAt(j) == '0') j++;
                res += ((j - i) * (j - i + 1)) >> 1;
                i = j;
            } else {
                i++;
                j++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new NumberOfSubstringsWithAllZeroes().stringCount("010010"));
    }
}
